package leetcode.d_1_99;

import java.util.Arrays;

// https://leetcode.cn/problems/next-permutation/description/
// 下一个排列
public class P31 {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return;
        }
        // 1. 从后往前找，找到第一个升序序列[i,j]
        int j = len-1;
        int i = len-1;
        for(; j>0; j--) {
            if (nums[j] > nums[j-1]) {
                i = j-1;
                break;
            }
        }
        // 1.1 如果没有找到，则直接倒序整个数组
        if (i == len-1) {
            Arrays.sort(nums);
            return;
        }

        // 2. 从[j,end]中从后往前找，找到第1个比nums[i]大的数，nums[swapIdx]
        int swapIdx = j;
        for (int k=len-1; k>=j; k--) {
            if (nums[k] > nums[i]) {
                swapIdx = k;
                break;
            }
        }

        // 2.2 交换nums[i]和nums[swapIdx]
        int temp = nums[swapIdx];
        nums[swapIdx] = nums[i];
        nums[i] = temp;

        // 3. 再把j后面的序列做升序排序
        Arrays.sort(nums, j, nums.length);
    }

    public static void main(String[] args) {
        P31 test = new P31();
        int[] nums = new int[]{1,2,3};
        test.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}
